﻿using System;
using System.Collections.Generic;
using System.Text;

namespace 二叉树___顺序结构存储
{
    class BiTree<T>
    {
        private T[] data;
        private int count = 0;
        public BiTree(int capacity)
        {
            data = new T[capacity]; 
        }
        public bool Add(T item)
        {
            if (count >= data.Length)
                return false;
            data[count] = item;
            count++;
            return true;
        }
        public void FirstTraversal()
        {
            FirstTraversal(0);
        }
        public void MiddleTraversal()
        {
            MiddleTraversal(0);
        }
        public void LastTraversal()
        {
            LastTraversal(0);
        }

        private void FirstTraversal(int index)
        {
            if (index >= count)
            {
                return;
            }
            int number = index + 1;
            if (data[index].Equals(-1))
            {
                return;
            }
            Console.Write(data[index] + " ");
            int leftNumber = number * 2;
            int rightNumber = number * 2 + 1;
            FirstTraversal(leftNumber - 1);
            FirstTraversal(rightNumber - 1);
        }

        private void MiddleTraversal(int index)
        {
            if (index >= count) return;

            int number = index + 1;

            if (data[index].Equals(-1)) return;

            int leftNumber = number * 2;
            int rightNumber = number * 2 + 1;

            MiddleTraversal(leftNumber - 1);

            Console.Write(data[index] + " ");

            MiddleTraversal(rightNumber - 1);
        }
        private void LastTraversal(int index)
        {
            if (index >= count) return;

            int number = index + 1;

            if (data[index].Equals(-1)) return;

            int leftNumber = number * 2;
            int rightNumber = number * 2 + 1;

            LastTraversal(leftNumber - 1);

            LastTraversal(rightNumber - 1);

            Console.Write(data[index] + " ");
        }
        public void LayerTraversal()
        {
            for (int i = 0; i < count; i++)
            {
                if (data[i].Equals(-1)) continue;
                Console.Write(data[i] + " ");
            }
            Console.WriteLine();
        }
    }
}
